1. Field of Inventions
This invention relates to the analysis of execution time and stack depth for computers.
2. Description of Prior Art
It is beneficial in real-time programs to know execution characteristics such as the maximum execution time, minimum execution time, and worst case stack depth. This is one way to verify that a real-time program will finish all tasks within its time and memory constraints.
The flow of a simple program diverts from a linear flow of execution by the use of a conditional branch. A conditional branch has two paths of execution that it may take based on some logical test. The first direction is the path taken when the conditional branch falls through to the next instruction. The second direction is when the conditional branch takes the branch to another instruction that does not follow it.
A common method of measuring execution time and stack depth is to use a logic analyzer. This works well only if the program executions in a simple linear fashion. It becomes more complex if the timing depends upon calculations or inputs. The problem is to catch the program in its worst case path. There is no way of knowing what that path is. If the path is known then it is usually very difficult to have the program execute it.
The problem with this method and all other methods that measure the performance of a processor is that they can not guarantee worst case results. The execution time and stack depth are discovered using a trial-and-error approach. They hope that the random set of events that causes the worst case execution time and stack depth to occur will happen while being examined.
A program that only simulates a processor has a similar disadvantage. It does not try every possible combination of execution paths because that is impractical. A simulator may try a large number of paths, especially at the extremes, but that does not prove the worst case results will be found.
The number of paths in a program that uses conditional branches is between N+1 and 2.sup.N where N is the number of conditional branches. A small program with 20 conditional branches would have between 21 and 1048576 possible separate paths through the program. It clearly becomes unrealistic to use conventional means to look at all of these paths to determine the worst case, especially in programs of significant size.